#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <Vector.hpp>
using namespace std;

class Solution
{
public:
    vector<vector<int>> threeSum(vector<int> &nums)
    {
        set<vector<int>> ans;
        if (nums.size() < 3)
        {
            return vector<vector<int>>();
        }
        sort(nums.begin(), nums.end());
        for (int i1 = 0; i1 < nums.size(); i1++)
        {
            if (nums[i1] > 0)
                break;
            int left = i1 + 1;
            int right = nums.size() - 1;
            while (left < right)
            {
                int sum = nums[i1] + nums[left] + nums[right];
                if (sum > 0)
                {
                    right--;
                }
                else if (sum < 0)
                {
                    left++;
                }
                else
                {
                    ans.insert({nums[i1], nums[left], nums[right]});
                    left++;
                    right--;
                    //不能直接退出循环,导致结果不全 可能存在更大的left和更小的right,符合条件
                    //break;
                }
            }
        }
        return std::vector<std::vector<int>>(ans.begin(), ans.end());
    }
};

int main()
{
    cout << "Code15" << endl;
    Solution s;
    vector<int> nums = {-1, 0, 1, 2, -1, -4};
    Print2DVector(s.threeSum(nums));
    return 0;
}

/*
vector<vector<int>> threeSum(vector<int> &nums)
{
    set<vector<int>> ans;
    if (nums.size() < 3)
    {
        return vector<vector<int>>();
    }
    for (int i1 = 0; i1 < nums.size(); i1++)
    {
        for (int i2 = i1 + 1; i2 < nums.size(); i2++)
        {
            for (int i3 = i2 + 1; i3 < nums.size(); i3++)
            {
                if (nums[i1] + nums[i2] + nums[i3] == 0)
                {
                    vector<int> temp = {nums[i1], nums[i2], nums[i3]};
                    sort(temp.begin(), temp.end());
                    ans.insert(temp);
                }
            }
        }
    }
    return std::vector<std::vector<int>>(ans.begin(), ans.end());
}
*/